#include <bits/stdc++.h>
using namespace std;

using llt = long long;
using vi = vector<int>;
using si = set<int>;
using vll = vector<llt>;

int const SZ = 10000001;

/// Fx[i] = SIGMA{mu(i/p)}
vector<llt> Fx;
vector<llt> Sum;
vector<bool> isComp; // isComp[i]表示i是否为合数
vector<llt> Primes; // Primes[i]是第i个质数
vector<int> Mobius; // 莫比乌斯函数

void init(){
    Primes.reserve(SZ);
    isComp.assign(SZ, false);   
   
    Mobius.assign(SZ, 0);
    Mobius[1] = 1;

    long long tmp;
    for(int i=2;i<SZ;++i){
        if(!isComp[i]){
            Primes.push_back(i);
            Mobius[i] = -1;
        }

        for(int j=0,n=Primes.size();j<n&&(tmp=i*(long long)Primes[j])<SZ;++j){
            isComp[tmp] = true;

            if(0 == i % Primes[j]){
                Mobius[tmp] = 0;
                break;
            }else{
                Mobius[tmp] = -Mobius[i];
            }
        }
    } 

    Fx.assign(SZ, 0);
    for(auto p : Primes){
        for(auto i=p;i<SZ;i+=p){
            Fx[i] += Mobius[i / p];
        }
    }

    Sum.assign(SZ, 0);
    for(int i=1;i<SZ;++i){
        Sum[i] = Sum[i - 1] + Fx[i];
    }
    return;   
}

int N, M;
void work(){
    cin >> N >> M;
    if(N > M) swap(N, M);
    llt ans = 0;
    for(int j,i=1;i<=N;i=j+1){
        auto x = N / i, y = M / i;
        j = min(N / x, M / y);
        ans += (Sum[j] - Sum[i - 1]) * x * y;
    }
    cout << ans << "\n";
    return;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);	
    init();
    int nofkase = 1;
	cin >> nofkase;
	while(nofkase--) work();
	return 0;
}